// 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
// 相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

function minimumTotal(triangle: number[][]): number {
  const dp: number[] = new Array(triangle.length + 1).fill(0); // dp数组，记得一定要初始化
  // 从底往上的动态规划算法
  for (let i = triangle.length - 1; i >= 0; i--) {
    // 行
    for (let j = 0; j < triangle[i].length; j++) {
      // 列
      dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];// 条件转移方程
    }
  }
  return dp[0];
}

// 这道题目是一道非常经典的动态规划的的题目。
// 这道题目我们主要的大致的方向是提供“自底向上”的规划计算，即先考虑最后一行的数据
// 我们先进行状态定义，dp[i]表示当前行第i列数据的最小路径和
// 我们要计算当前行的所处列的最小路径，只需要知道之前计算相邻两列的较小值加上当前值
// 这就得到了条件转移方程
// 即在动态规划算法的进行过程中，假设我们需要计算第 i 行的数据，我们只需要知道第 i+1 行的数据即可
// 因为只需要知道上一行，所以我们就只需要声明一维的动态规划数组即可
// 这里别忘记了最下方一行也要参与计算，所以需要进行初始化赋值，这里不要忘了
